package org.raymond.iworks.study.basic.algorithm.sort;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 快速排序:
 * 是对冒泡排序的一种改进.基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,
 * 其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序,
 * 整个排序过程可以递归进行,以此达到整个数据变成有序序列.
 */

import java.util.Arrays;

/**
 * 示意图:
 * 8,9,1,7,2,3,5,4,6,0
 * 以5为基准:
 *   左:1,2,3,4,0
 *   以3为基准:
 *     左:1,2
 *     右:4,0
 *   右:8,9,7,6
 *   以7为基准:
 *     左:6,
 *     右:8,9
 *  1,2,3,4,0,5,6,7,8,9
 */
public class QuickSortTest {
    public static void main(String[] args) {
        int[] arr = newArr();
        //arr = new int[]{3, 9, -1, 10, -2};
        //arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        arr = new int[]{-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        long start = System.nanoTime();
        qksort(arr, 0, arr.length-1);
        long end = System.nanoTime();
        System.out.printf("快速排序结果:%s\n", Arrays.toString(arr));
        // post: 22,153,200 纳秒,约22毫秒, 100,000个元素
        // post: 22,087,008,200 纳秒,约22秒, 100,000,000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        /*
        arr = newArr();
        arr = new int[]{-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        start = System.nanoTime();
        SelectSortTest.jdkSort(arr);
        end = System.nanoTime();
        System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 47,220,300 纳秒, 约50毫秒, 100,000个元素的数组
        // post: 15,091,233,500 纳秒, 约15秒, 1亿个元素
        System.out.printf("jdksort 耗时:%d\n", (end-start));
         */
    }

    public static int[] newArr(){
        int[] arr = new int[100_000_000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*Integer.MAX_VALUE);
        }
        return arr;
    }

    public static void qksort(int[] arr, int left, int right){
        int tmp=0;
        int l = left;
        int r = right;
        // 中轴左边放较小的值,右边放较大的值
        int pivot = arr[(left+right)/2];

        while(l<r){
            // 找出左边比pivot大的值的下标
            while(arr[l]<pivot){
                l++;
            }
            // 找出右边比pivot小的值的下标
            while(arr[r]>pivot){
                r--;
            }
            // 此时已经完成分组,确保左游标不越过中轴
            if(l>=r){
                break;
            }
            // 将左边较大的值与右边较小的值互换
            tmp = arr[l];
            arr[l]=arr[r];
            arr[r]=tmp;

            // 交换完成后,若左边的值与pivot相等,则右游标向中心靠拢
            if(arr[l]==pivot){
                r--;
            }
            // 交换完成后,若右边的值与pivot相等,则左游标向中心靠拢
            if(arr[r]==pivot){
                l++;
            }
        }
        // 若左游标与右游标重叠,则必须错开,否则会栈溢出
        if(l==r){
            l++;
            r--;
        }
        // 若左边界还在右游标左边,即左边界与右游标之间还存在元素,则左递归
        if(left<r){
            qksort(arr, left, r);
        }
        // 若右边界还在左游标右边,即右边界与左游标之间还存在元素,则右递归
        if(right>l){
            qksort(arr, l, right);
        }
    }
}
